# 颜色分类：https://leetcode-cn.com/problems/sort-colors/

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
            可以按照分区排序， 选择快速排序使用的 三路快排的分区逻辑
        """
        n = len(nums) - 1

        less = i = 0
        great = n
        while i <= great:
            if nums[i] == 0:
                nums[i], nums[less] = nums[less], nums[i]
                less += 1
                i += 1
            elif nums[i] == 1:
                i += 1
            elif nums[i] == 2:
                nums[i], nums[great] = nums[great], nums[i]
                great -= 1

# 按照计数排序进行做
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
            按照计数排序进行做
        """
        n = len(nums)
        count = [0] * (max(nums) + 1)

        for i in nums:
            count[i] += 1
        
        cur = 0
        for i, cut in enumerate(count):
            for j in range(cut):
                nums[cur] = i
                cur += 1